/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._441;

/**
 * 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
 * <p>
 * 给定一个数字 n，找出可形成完整阶梯行的总行数。
 * <p>
 * n 是一个非负整数，并且在32位有符号整型的范围内。
 * <p>
 * 示例 1:
 * <p>
 * n = 5
 * <p>
 * 硬币可排列成以下几行:
 * ¤
 * ¤ ¤
 * ¤ ¤
 * <p>
 * 因为第三行不完整，所以返回2.
 * 示例 2:
 * <p>
 * n = 8
 * <p>
 * 硬币可排列成以下几行:
 * ¤
 * ¤ ¤
 * ¤ ¤ ¤
 * ¤ ¤
 * <p>
 * 因为第四行不完整，所以返回3.
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._441
 * @ClassName: ArrangingCoins
 * @Author: linyaonan
 * @Date: 2019/12/30 10:45
 */
public class ArrangingCoins {

    public int arrangeCoins(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n >= 2147450880) {
            return 65535;
        }
        if (n >= 2147385345) {
            return 65534;
        }
        if (n >= 2147319811) {
            return 65533;
        }
        int t = (int) Math.sqrt((long) n * 2);
        for (int i = t; i < 65535; i++) {
            if (pCount(i) > n) {
                return i-1;
            }
        }
        return 1;
    }

    /**
     * 需要注意一些相乘后越界的情况
     * @param n
     * @return
     */
    public int arrangeCoins2(int n) {
        // 特殊边界
        if (n <= 0) {
            return 0;
        }
        if (n >= 2147450880) {
            return 65535;
        }
        if (n >= 2147385345) {
            return 65534;
        }
        if (n >= 2147319811) {
            return 65533;
        }
        int l = 1;
        int r = 65535;

        while (l <= r) {
            long mid = l + ((r - l) >> 1);
            long midP = (((1 + mid) * (mid)) >> 1);
            if (midP >= n && (((1 + mid + 1) * (mid + 1)) >> 1) < n) {
                return (int) midP;
            } else {
                if (midP < n) {
                    l = (int)mid + 1;
                } else {
                    r = (int)mid - 1;
                }
            }
        }

        if ((((1 + (long) l) * (l)) >> 1) == (long) n) {
            return l;
        } else {
            return l - 1;
        }
    }

    private long pCount(int n) {
        if (n == 1) {
            return 1;
        } else {
            long p = (long) n * (n + 1);
            return p / 2;
        }
    }
}
